package com.example.demo.tixiban;

import java.util.Arrays;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2022/2/13 14:53
 */
public class Tree_先序遍历中序遍历生成树 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     *        1
     *     2    3
     *   4  5  6 7
     *
     *    fisrt    1 2 4 5  3 6 7
     *    second   4 2 5 1  6 3 7
     *
     *  先序数组 fisrt 中序数组 second
     *  从fisrt 去scond中寻找到值， 这个值的左右两边 分别是左子树，右子树
     *  然后左子树 右子树再分别递归 拼接到当前的tree中
     *
     * @param first
     * @return
     */
    public static TreeNode createTree(int [] first, int [] second){
        if(first.length <=0 || second.length <=0){
            return null;
        }

        int middleIndex = 0;
        for(int i =0;i<second.length;i++){
            if(first[0] == second[i]){
                middleIndex = i;
                break;
            }
        }
        TreeNode treeNode = new TreeNode(first[0]);
        int [] first_left = Arrays.copyOfRange(first,1,middleIndex+1);
        int [] first_right = Arrays.copyOfRange(first,middleIndex+1 >= first.length ? first.length : middleIndex+1,first.length);
        int [] second_left = Arrays.copyOfRange(second,0,middleIndex);
        int [] second_right = Arrays.copyOfRange(second,middleIndex+1 >= second.length ? second.length : middleIndex+1,second.length);

        treeNode.left = createTree(first_left,second_left);
        treeNode.right = createTree(first_right,second_right);
        return treeNode;
    }

    /**
     *   指针
     *        1
     *     2    3
     *   4  5  6 7
     *
     *    fisrt    1 2 4 5  3 6 7
     *    second   4 2 5 1  6 3 7
     *
     *    first  2  4  5
     *    下标: 1  2  3
     *          L1    R1
     *    first 范围是 [L1+1,L1+middle-L2] [L1+middle-L2+1,R1]
     *
     *   second 4  2  5
     *    下标: 0  1  2
     *         L2  middle R2
     *
     *
     *
     * @param first
     * @param L1
     * @param R1
     * @param second
     * @param L2
     * @param R2
     * @return
     */
    public static TreeNode createTree(int [] first,int L1,int R1, int [] second, int L2, int R2){
        if(L1 > R1){
            return null;
        }
        TreeNode treeNode = new TreeNode(first[L1]);
        if(L1 == R1){
            return treeNode;
        }
        int middleIndex = 0;
        for(int i =L2; i<=R2;i++){
            if(first[L1] == second[i]){
                middleIndex = i;
                break;
            }
        }
        treeNode.left = createTree(first,L1+1,L1+middleIndex-L2,second,L2,middleIndex-1);
        treeNode.right = createTree(first,L1+middleIndex-L2+1,R1,second,middleIndex+1,R2);
        return treeNode;
    }


    public static void main(String[] args) {
        int [] first = {1,2,4,5,3,6,7};
        int [] second = {4,2,5,1,6,3,7};
        // TreeNode tree = createTree(first, second);
        // System.out.println(tree.val);

        TreeNode tree2 = createTree(first,0,first.length-1, second,0,second.length-1);
        System.out.println(tree2.val);
    }






}
